package A一周刷爆LeetCode.B基础提升.CKMP与Manacher算法;

/**
 * @author wei.zhao
 * @description: Manacher算法
 * @date 2022年09月28日 14:39
 */
public class Code03_Manacher改进后写法 {

    public static void main(String[] args) {
        String str1 = "abc1234321abhj11222211";
        System.out.println(maxLcpsLength(str1));
    }

    public static int maxLcpsLength(String str) {
        if (null == str || str.length() == 0) {
            return 0;
        }
        char[] chars = manacherString(str);
        // 回文半径数组
        int[] arr = new int[chars.length];
        // 所扩到最右位置时的中心点
        int C = -1;
        // 所扩到最右位置
        int R = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < chars.length; i++) {
            int r = i < R ? Math.min(arr[2 * C - i], R - i) : 1;
            while (i - r > -1 & i + r < arr.length && chars[i - r] == chars[i + r]) {
                r++;
            }
            arr[i] = r;
            if (i + r - 1 > R) {
                C = i;
                R = i + r - 1;
            }
            max = Math.max(max, r);
        }
        return max - 1;
    }

    /**
     * 字符间加'#'，处理成特殊字符数组
     */
    public static char[] manacherString(String str) {
        char[] tempChars = str.toCharArray();
        char[] chars = new char[2 * str.length() + 1];
        for (int i = 0; i < chars.length; i++) {
            if (i % 2 == 0) {
                chars[i] = '#';
            } else {
                chars[i] = tempChars[i / 2];
            }
        }
        return chars;
    }

}
